home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_10 / 1010114a < prev    next >
Text File  |  1992-08-12  |  4KB  |  180 lines
  1. /*
  2.  * Listing 1
  3.  *
  4.  * COMPRS.C - Ross Data Compression (RDC)
  5.  *            compress function
  6.  *
  7.  * Written by Ed Ross, 1/92
  8.  *
  9.  * compress inbuff_len bytes of inbuff into outbuff
  10.  * using hash_len entries in hash_tbl.
  11.  *
  12.  * return length of outbuff, or "0 - inbuff_len"
  13.  * if inbuff could not be compressed.
  14.  *
  15. */
  16.  
  17. #include <string.h>
  18.  
  19. typedef unsigned char uchar;    /*  8 bits, unsigned */
  20. typedef unsigned int  uint;     /* 16 bits, unsigned */
  21.  
  22. int rdc_compress(uchar *inbuff, uint inbuff_len,
  23.                  uchar *outbuff,
  24.                  uchar *hash_tbl[], uint hash_len)
  25. {
  26. uchar   *in_idx = inbuff;
  27. uchar   *inbuff_end = inbuff + inbuff_len;
  28. uchar   *anchor;
  29. uchar   *pat_idx;
  30. uint    cnt;
  31. uint    gap;
  32. uint    c;
  33. uint    hash;
  34.  
  35. uint    *ctrl_idx = (uint *) outbuff;
  36. uint    ctrl_bits;
  37. uint    ctrl_cnt = 0;
  38.  
  39. uchar   *out_idx = outbuff + sizeof(uint);
  40. uchar   *outbuff_end = outbuff + (inbuff_len - 48);
  41.  
  42.   /* skip the compression for a small buffer */
  43.  
  44.   if (inbuff_len <= 18)
  45.   {
  46.     memcpy(outbuff, inbuff, inbuff_len);
  47.     return 0 - inbuff_len;
  48.   }
  49.  
  50.   /* adjust # hash entries so hash algorithm can
  51.      use 'and' instead of 'mod' */
  52.  
  53.   hash_len--;
  54.  
  55.   /* scan thru inbuff */
  56.  
  57.   while (in_idx < inbuff_end)
  58.   {
  59.     /* make room for the control bits
  60.        and check for outbuff overflow */
  61.  
  62.     if (ctrl_cnt++ == 16)
  63.     {
  64.       *ctrl_idx = ctrl_bits;
  65.       ctrl_cnt = 1;
  66.       ctrl_idx = (uint *) out_idx;
  67.       out_idx += 2;
  68.  
  69.       if (out_idx > outbuff_end)
  70.       {
  71.         memcpy(outbuff, inbuff, inbuff_len);
  72.         return 0 - inbuff_len;
  73.       }
  74.     }
  75.  
  76.     /* look for rle */
  77.  
  78.     anchor = in_idx;
  79.     c = *in_idx++;
  80.  
  81.     while (in_idx < inbuff_end
  82.            && *in_idx == c
  83.            && (in_idx - anchor) < 4114)
  84.         in_idx++;
  85.  
  86.     /* store compression code if character is
  87.        repeated more than 2 times */
  88.  
  89.     if ((cnt = in_idx - anchor) > 2)
  90.     {
  91.       if (cnt <= 18)          /* short rle */
  92.       {
  93.         *out_idx++ = cnt - 3;
  94.         *out_idx++ = c;
  95.       }
  96.       else                    /* long rle */
  97.       {
  98.         cnt -= 19;
  99.         *out_idx++ = 16 + (cnt & 0x0F);
  100.         *out_idx++ = cnt >> 4;
  101.         *out_idx++ = c;
  102.       }
  103.  
  104.       ctrl_bits = (ctrl_bits << 1) | 1;
  105.  
  106.       continue;
  107.     }
  108.  
  109.     /* look for pattern if 2 or more characters
  110.        remain in the input buffer */
  111.  
  112.     in_idx = anchor;
  113.  
  114.     if ((inbuff_end - in_idx) > 2)
  115.     {
  116.       /* locate offset of possible pattern
  117.          in sliding dictionary */
  118.  
  119.       hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^
  120.           ((in_idx[0] >> 4) | (in_idx[2] << 4)))
  121.           & hash_len;
  122.  
  123.       pat_idx = hash_tbl[hash];
  124.       hash_tbl[hash] = in_idx;
  125.  
  126.       /* compare characters if we're within 4098 bytes */
  127.  
  128.       if ((gap = in_idx - pat_idx) <= 4098)
  129.       {
  130.         while (in_idx < inbuff_end
  131.                && pat_idx < anchor && *pat_idx == *in_idx
  132.                && (in_idx - anchor) < 271)
  133.         {
  134.           in_idx++;
  135.           pat_idx++;
  136.         }
  137.  
  138.         /* store pattern if it is more than 2 characters */
  139.  
  140.         if ((cnt = in_idx - anchor) > 2)
  141.         {
  142.           gap -= 3;
  143.  
  144.           if (cnt <= 15)          /* short pattern */
  145.           {
  146.             *out_idx++ = (cnt << 4) + (gap & 0x0F);
  147.             *out_idx++ = gap >> 4;
  148.           }
  149.           else                    /* long pattern */
  150.           {
  151.             *out_idx++ = 32 + (gap & 0x0F);
  152.             *out_idx++ = gap >> 4;
  153.             *out_idx++ = cnt - 16;
  154.           }
  155.  
  156.           ctrl_bits = (ctrl_bits << 1) | 1;
  157.  
  158.           continue;
  159.         }
  160.       }
  161.     }
  162.  
  163.     /* can't compress this character
  164.        so copy it to outbuff */
  165.  
  166.     *out_idx++ = c;
  167.     in_idx = ++anchor;
  168.     ctrl_bits <<= 1;
  169.   }
  170.  
  171.   /* save last load of control bits */
  172.  
  173.   ctrl_bits <<= (16 - ctrl_cnt);
  174.   *ctrl_idx = ctrl_bits;
  175.  
  176.   /* and return size of compressed buffer */
  177.  
  178.   return out_idx - outbuff;
  179. }
  180.